Encoding an information sequence at a transmitter and decoding the received sequence at a receiver is one way to reduce errors caused by undesirable channel/environment conditions. For example, convolutional encoding is an error-correcting scheme, which passes an information sequence to be transmitted through a linear finite state shift register to generate an encoded information sequence. The Viterbi algorithm is recognized as the optimal algorithm for decoding a received convolutionally encoded information sequence at the receiver. (See, A. J. Viterbi, “Error bounds for convolutional coding and an asymptotically optimum decoding algorithm,” IEEE Trans. Info. Theory, pp. 260-269, April 1967). The Viterbi algorithm has many applications, including digital communications, speech recognition and magnetic recording, among others.
A convolutional encoder can be implemented as a finite state machine in which the transitions between states are determined by the input sequence. Thus, a Viterbi decoder can operate by first estimating possible states and transitions between states (i.e., to obtain a code trellis diagram) and then estimating the most likely transmitted sequence using trace-back operations. Theoretically, the Viterbi decoder can use the entire sequence input to the decoder to optimally estimate the most likely transmitted sequence but, in practice, it is not desirable to wait for the entire sequence before starting to decode. Thus, in one implementation, the Viterbi decoder can be configured to estimate one symbol for every L symbols input to the decoder. L is referred to as the “traceback length” and, for example, can be chosen as five times the constraint length of the convolutional code.
Various techniques can be applied to increase Viterbi decoder speed with respect to the number of symbols decoded per unit time. For example, look-ahead architectures can be employed that increase throughput by calculating a number of metrics at each clock cycle. (See, Lin et al., “Algorithms and architectures for concurrent Viterbi decoding,” Proc. ICC '89, vol. 2, pp. 836-840, June 1989). Additionally, a sliding-block Viterbi decoder (SBVD) can be employed to decode a number of symbols (bits) each clock cycle. In other words, instead of decoding one bit per unit time, the SBVD decodes M bits per unit time. (See, Black et. al., “A 1-Gb/s Four-State, Sliding Block Viterbi Decoder,” IEEE Journal of Solid-State Circuits, vol. 32, no. 6, pp. 797-805, June 1997).